1. Field of the Invention
This invention relates to transmissions of digital information between a sending unit and a receiving unit, and more particularly, to methods of detecting and recovering from errors in transmitting digital information from a sending unit to a receiving unit and to methods of detecting transmission errors between an upper processor and a lower processor in a base station of a digital cellular system.
2. Description of the Related Art
Errors can occur in a transmission of digital information from a sending unit to a receiving unit. Such errors occur in two types: errors in which a part of the information transmitted is not received, i.e., information losses, and errors consisting in corruption of information during the transmission process. In what follows, an error of the second or "corruption" type will be referred to as an error, while an error of the first type will be referred to as missed information or a loss of information.
Various methods are well known for detecting and compensating for errors and losses in the transmission of digital information. These methods generally address error detection and correction in specific contexts and therefore include inherent limitations that prevent them from being suitable for a wider range of fields of application. For example, U.S. Pat. No. 5,007,054, entitled "Network and Protocol for Real-Time Control of Machine Operations" and granted to Lee et al., discloses a communication network for connecting microprocessor controllers in a mail processing system. Each message sent between microprocessors comprises a message word count followed by uninterrupted message data. A receiving microprocessor sends back a positive acknowledgment word when it detects that the message is error-free and has as many words as indicated by the message word count sent initially. A known arithmetic checksum method is used to check for errors. The receiving microprocessor sends a negative acknowledgment to indicate missing words or errors, and the sending microprocessor responds by retransmitting the entire message.
The efficiency of this system benefits from the fact that a receiving unit only transmits an acknowledgment after the entire message has been transmitted. On the other hand, the messages involved are short: no more than 33 words in length. In systems with higher-level communications, messages are typically longer and division into packets often occurs, retransmission of an entire message is impractical. Moreover, where both sending and receiving units have significant processing capabilities, greater efficiency could be realized by a fuller integration of the two units in the error-checking process.
A frequently-used approach to detecting errors in digital transmissions involves computation of checksums. Such computation typically produces one or more checksum values by adding together the numerical values of the words in a unit of information. The unit is checked for errors after transmission by re-summing the words along with the checksum values, in any of various well-known procedures. The process of producing and using checksums to perform error checking can itself require significant computational resources. Different approaches have been suggested for generating checksums. For example, U.S. Pat. No. 5,247,524, entitled "Method for Generating a Checksum" and granted to Callon, discloses a method for computing a checksum for a bit string in a data packet. The method involves grouping the bit string into contiguous groups and sequentially producing a checksum component for each group. A final checksum for the entire bit string is computed as an accumulation of the checksum components.
Callon'524 thus shows an interesting alternative approach to computing checksums. Using checksums for error checking, though, also requires checking a data unit against an associated checksum after transmission. It would be desirable to have an error checking method that requires less overhead in the combined process of producing checksums and checking for errors with them. Ideally, such a method would make use of other information produced otherwise to carry out the transmission in further reducing the computational overhead.
U.S. Pat. No. 5,506,958, entitled "Error Detection for Parallel Data Transfer Between a Processor and a Peripheral Device by Comparing Registers Storing a Sum of Values in Bytes of Data Transferred" and granted to Myran, provides an approach for performing error checking that allows increased data transfer rates. This reference discloses a method and apparatus for detecting errors in data transfer between a computer and a peripheral device such as a printer. The transmission occurs through an interface port that includes a FIFO DRAM buffer and a memory location for a checksum. Before transferring a block of data to the FIFO DRAM, the computer initializes an internal checksum variable and the interface checksum to the same initial value, typically zero. As each word of data is transferred, the computer adds to the internal checksum variable the value of the word as transmitted and adds to the interface checksum the value of the word as received. When the entire block has been transmitted, the computer compares the two checksum values: equal values means no transmission error, while unequal values means an error occurred.
This system concurrently accumulates checksums for a message both as transmitted and as received, thus utilizing hardware parallelism to mitigate the error checking bottleneck. However, it does not overcome the need to compute checksums for both ends of the communication channel. Also, because the computer must carry out the accumulation procedure for both checksum values, the Myran procedure still entails two serial calculations.
Information losses present a related and persistent problem that requires remediation for reliable high speed digital information transmission. Like error recovery, a first step in remediating partial information loss consists in determining that such a loss has occurred. U.S. Pat. No. 5,577,046, entitled "Automatic Information Request" and granted to Diachina et al., provides one approach for detecting information loss. This reference shows a method for a cellular telephone system base station to obtain from a mobile station a report of the status of the individual packets comprising a message sent from the base station to the mobile station. The base station sends the message as a sequence of packets and also sends a polling request directing the mobile station to send information on the packets it has received without error. The mobile station responds by sending a bit map with length corresponding to the number of packets in the message (up to a maximum of 32). Each bit in the bit map corresponds to a packet in the message previously sent by the base station, and the values of the bits indicate RECEIVED or NOT RECEIVED according to whether the mobile station received the corresponding packet without errors.
The Diachina base station configuration provides for polling requests to be sent before an entire message has been transmitted, which necessarily adds to the overhead from loss detection by requiring several loss determination procedures. Moreover, in this system the bit map serves only as a format for communicating message packet status to the base station, rather than as a means by which the mobile station determines that it needs retransmission of certain packets. In fact, the determination that some packets must be retransmitted, and which ones, occurs at the base station, not the mobile station. Also, this system does not adapt its response to different levels of information loss severity.
I have found that a need exists for a method for increasing the integrity of digital transmissions while requiring minimal additional system resources and maintaining high data transfer rates. This method should be suitable for use with high-level communication systems using packetized data transfer. Desirably, such a method would also reduce redundancy in error checking calculations and loss detection procedures. Ideally, such a method would utilize hardware parallelism to reduce overhead and would have automatic adaptation to the severity of disruption incurred in a transmission.